public class Search {
    public static int[] arr = new int[]{1, 4, 5, 6, 7, 9, 14, 18, 19, 20, 24, 26, 29, 35, 36, 54, 99};
    public static int[] ints = new int[30];

    public static void main(String[] args) {

        // halfSearch(99, 0, arr.length);
        for (int i : arr) {
            hashPush(i, ints);
        }
        System.out.println(ints);
        int i = hashSearch(21);
        System.out.println(i);

    }

    /**
     * 折半查找
     */
    public static void halfSearch(int target, int start, int end) {
        if (start == end || start + 1 == end) {
            System.out.println("目标不存在");
            return;
        }
        int mid = (start + end) / 2;
        if (arr[mid] == target) {
            System.out.println("找到目标，下标：" + mid);
        } else if (arr[mid] < target) {
            halfSearch(target, mid, end);
        } else if (arr[mid] > target) {
            halfSearch(target, start, mid);
        }
    }

    public static int hashSearch(int a) {
        int mod = a % 15;
        // 具有hash冲突的查找
        while (arr[mod] != a && arr[mod] != 0) {
            mod = mod + 1;
            if (mod >= arr.length) {
                return -1;
            }
        }
        return mod;
    }

    public static void hashPush(int a, int[] arr) {
        // 求余法
        int mod = a % 15;
        // 解决哈希冲突
        while (arr[mod] != 0) {
            mod = mod + 1;
        }
        arr[mod] = a;
    }

}
